package topology;

import java.util.*;

/**
 * 207. 课程表
 */
public class P207 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1. 初始化map
        Map<String, Set<String>> map = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            map.put("" + i, new HashSet<>());
        }
        // 2. 遍历依赖关系
        for (int i = 0; i < prerequisites.length; i++) {
            map.get(prerequisites[i][0] + "").add(prerequisites[i][1] + "");
        }

        // 3. 遍历Map
        boolean[] courseLearned = new boolean[numCourses];
        while (map.size() > 0) {
            boolean adjusted = false;
            Iterator<Map.Entry<String, Set<String>>> iterator = map.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<String, Set<String>> entry = iterator.next();
                boolean flag = true;
                for (String course : entry.getValue()) {
                    if (!courseLearned[Integer.parseInt(course)]) {
                        flag = false;
                    }
                }
                if (flag) {
                    courseLearned[Integer.parseInt(entry.getKey())] = true;
                    iterator.remove();
                    adjusted = true;
                }
            }
            if (!adjusted) {
                break;
            }
        }
        // 4. 结果
        if (map.size() == 0) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        int[][] prerequisites = new int[][]{
                {1, 0},
                {0, 1}
        };
        boolean flag = new P207().canFinish(2, prerequisites);
        System.out.println(flag);
    }
}
